package com.lisp.algorithm.sort;

import java.util.ArrayList;

import com.lisp.algorithm.util.SortUtil;

public class BucketSort {

    public static void main(String[] args) {
        SortUtil.test(RadixSort::radixSort);
    }
    
    @SuppressWarnings("rawtypes")
    public static void bucketSort(int a[]) {
        int max = 1000;
        int bucketNum = max/10 + 1;
        ArrayList[] buckets = new ArrayList[bucketNum];
        for(int i=0; i<buckets.length; i++) {
            buckets[i] = new ArrayList();
        }
        
        for(int i=0; i<a.length; i++) {
            insert(buckets[a[i]/10], a[i]);
        }
        
        int idx=0;
        for(int i=0; i<buckets.length; i++) {
            for(Object val : buckets[i]) {
                a[idx++] = (Integer) val;
            }
        }
    }
    
    @SuppressWarnings({ "rawtypes", "unchecked" })
    private static void insert(ArrayList bucket, int val) {
        int i=bucket.size()-1;
        for(; i>=0; i--) {
            if(((Integer) bucket.get(i)) <= val) {
                break;
            }
        }
        
        bucket.add(i+1, val);
    }
}